package algorithm.leetcode.I1to100;

import java.util.LinkedList;

/**
 * 思路: 递归,拿到上一层的解之后递推到本层解
 * 递推关系: 例  11 2 3 22 3
 * 计算char变换的位置和长度 (2,1), (1,2), (1,3), (2,2), (1,3)
 */

public class Q38 {

    public String countAndSay(int n) {
        if (n == 1) return "1";

        String[] chars = (countAndSay(n - 1) + "0").split("");

        LinkedList<int[]> changeIndex = new LinkedList<>();
        int start = 0;

        for (int i = 1; i < chars.length; i++) {
            if (!chars[i].equals(chars[i-1])) {
                changeIndex.add(new int[]{i-start, Integer.parseInt(chars[i-1])});
                start = i;
            }
        }

        StringBuilder result = new StringBuilder("");
        for (int[] index : changeIndex) {
            result.append(index[0]).append(index[1]);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Q38 threeEight = new Q38();
        System.out.println(threeEight.countAndSay(8));
    }

}
